#include<stdio.h>
#include<stdlib.h>

/*
 * 创建一个完全二叉树
 * 实现三种遍历方式
 *
 * 作者：Tmacy
 * 时间：2013-11-27
 *
 */
#define STACK_SIZE 16

typedef int datatype;

typedef struct _tree{
    datatype data;
    struct _tree *lchild,*rchild;
}bitree;


void preorder_recursion(bitree *root);

void preorder_stack(bitree *root);

void inorder_recursion(bitree * root);

void inorder_stack(bitree *root);

void post_order_recursion(bitree *);

void postorder_stack(bitree *root);

bitree* create_bitree(int i,int n);

int main(int argc, const char *argv[])
{
    bitree * root = create_bitree(1,10);

    printf("preorder is :\n");
//    preorder_recursion(root);
    preorder_stack(root);
    putchar(10);

    printf("inorder is :\n");
//    inorder_recursion(root);
    inorder_stack(root);
    putchar(10);

    printf("postorder is :\n");
//    post_order_recursion(root);
    postorder_stack(root);
    putchar(10);
    
    return 0;
}
/*
 * 创建完全二叉树
 * i表示树根节点编号，初始值为1
 * n表示二叉树节点总数
 * 返回值：返回创建的二叉树树根
 *
 */
bitree* create_bitree(int i,int n){

    bitree * root;
    root = (bitree*)malloc(sizeof(bitree));
    root->data = i;

    if(2 * i <= n){
        root->lchild = create_bitree(2 * i ,n);
    }else{
        root->lchild = NULL;
    }

    if(2 * i + 1 <= n){
        root->rchild = create_bitree(2 * i + 1 , n);
    }else{
        root->rchild = NULL;
    }

    return root;

}
// 递归方式实现先根遍历
void preorder_recursion(bitree *root){
    if(root == NULL)
        return ;
    printf("%d ",root->data);
    preorder_recursion(root->lchild);
    preorder_recursion(root->rchild);
}
//采用栈的方式实现先根遍历
void preorder_stack(bitree *root){
    if(root == NULL)
        return ;
    bitree * stack [STACK_SIZE];
    bitree *temp;
    int stack_top = 0;
    
    stack[stack_top++] = root;                  //树根入栈
    while(stack_top){
        temp = stack[--stack_top];          
        printf("%d ",temp->data);
        if(temp->rchild){
            stack[stack_top++] = temp->rchild;  //左孩子入栈
        }
        if(temp->lchild){
            stack[stack_top++] = temp->lchild;  //右孩子入栈
        }
    }
}
//递归实现中根遍历
void inorder_recursion(bitree *root){
    if(root == NULL){
        return ;
    }

    inorder_recursion(root->lchild);
    printf("%d ",root->data);
    inorder_recursion(root->rchild);
}
//采用栈的方式实现中根遍历
void inorder_stack(bitree *root){
    if(root == NULL)
        return ;
    bitree * stack [STACK_SIZE];
    bitree *temp;
    int stack_top = 0;
    
    temp = root;

    while(stack_top || temp != NULL){
        if(temp){
            stack[stack_top++] = temp;
            temp = temp->lchild;
        }else{
            temp = stack[--stack_top];
            printf("%d ",temp->data);
            temp = temp->rchild;
        }
    }
}

// 递归实现后根遍历
void post_order_recursion(bitree *root){
    if(root == NULL)
        return;

    post_order_recursion(root->lchild);
    post_order_recursion(root->rchild);
    printf("%d ",root->data);

}

//采用栈的方式实现后根遍历
void postorder_stack(bitree *root){
    if(root == NULL)
        return ;
    bitree * stack [STACK_SIZE];
    bitree *temp = root;
    int stack_top = 0;
    int s[STACK_SIZE] = {0};

}
